Birtukan quyết định tham gia một đảng chính trị để giúp mang lại sự thay đổi, bao gồm cả việc thừa nhận luật pháp và tôn trọng hoàn toàn việc thực thi hiến pháp. Bà gia nhập Rainbow Ethiopia: Phong trào Dân chủ và Đảng Công bằng Xã hội, và sau đó, Liên minh vì Thống nhất và Dân chủ (CUD). Trong cuộc bầu cử năm 2005, đảng của bà đã giành được một phần ba số ghế. Các đảng viên tin rằng họ sẽ giành được nhiều ghế hơn nếu không bỏ phiếu và tính bất thường. Sau cuộc bầu cử, đảng cầm quyền bắt đầu vây bắt các nhà lãnh đạo đảng đối lập, Mideksa, người bị kết án vì cố gắng lật đổ trật tự hiến pháp và bị kết án chung thân. Bà đã được ân xá vào năm 2007 sau các cuộc đàm phán kéo dài và sau đó, cùng với các nhà lãnh đạo khác của phe đối lập, đã ở tù được 18 tháng.[5]

Mideksa sau đó thành lập UDJ (Thống nhất vì Dân chủ và Công lý) với cùng các nguyên tắc hướng dẫn CUD. Nhu cầu có tên đảng mới xuất phát từ thực tế là ủy ban bầu cử của đảng cầm quyền được trao cho một nhóm chia rẽ từ CUD (còn gọi là Kinijit). Birtukan được bầu làm chủ tịch của UDJ, với mục tiêu mang lại sự thay đổi ở Ethiopia bằng các biện pháp hòa bình. [ <span title="This claim needs references to reliable sources. (July 2012)">cần dẫn nguồn</span> ]